package com.huawei;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

/**
 * Description: HJ50 四则运算
 * 3+2*{1+2*[-4/(8-6)+7]}
 *
 * @author weiruibai.vendor
 * Date: 2022/8/17 10:30
 */
public class HJ50 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = "3+2*(1+2*(-4/(8-6)+7))";  //br.readLine();
        str = str.replace("[", "("); // 将括号统一为小括号
        str = str.replace("]", ")");
        str = str.replace("{", "(");
        str = str.replace("}", ")");
        System.out.println(solve_v1(str));
        System.out.println(solve_v2(str));
    }

    /**
     * 自己参考solve_v1写的
     *
     * @param s
     * @return
     */
    public static int solve_v2(String s) {
        int ans = 0;
        char[] chars = s.toCharArray();
        int N = chars.length;
        Stack<Integer> calcStack = new Stack<>();
        int num = 0;
        char preSym = '+';
        for (int i = 0; i < N; i++) {
            char ch = chars[i];
            // 数字
            if (Character.isDigit(ch)) {
                num = num * 10 + (ch - '0');
            } else if ('(' == ch) {
                // 处理这个括号之间的数
                int j = i + 1;
                int symbol = 1;
                while (symbol > 0) {
                    if ('(' == chars[j]) symbol++;
                    if (')' == chars[j]) symbol--;
                    j++;
                }
                // 计算i+1~j-1之间的数
                num = solve_v2(s.substring(i + 1, j - 1));
                // 重新设置i起点
                i = j - 1;
            }
            if (!Character.isDigit(ch) || i == N - 1) {
                if ('+' == preSym) {
                    calcStack.add(num);
                } else if ('-' == preSym) {
                    calcStack.add(-num);
                } else if ('*' == preSym) {
                    int multi = calcStack.pop() * num;
                    calcStack.add(multi);
                } else if ('/' == preSym) {
                    int minus = calcStack.pop() / num;
                    calcStack.add(minus);
                }
                preSym = ch;
                num = 0;
            }
        }
        while (!calcStack.isEmpty()) {
            ans += calcStack.pop();
        }
        return ans;
    }

    /*
      递归思想，从内到外处理括号，用栈存放操作数和中间结果。
      +运算符直接入栈，-运算符乘-1入栈，乘除运算符计算完入栈，
      最终栈内所有数相加即是结果
    */
    public static int solve_v1(String s) {
        Stack<Integer> nums = new Stack<>(); // 存放操作数和中间计算结果
        char[] expr = s.toCharArray();
        // 初始数字
        int num = 0;
        // 初始运算符（让第一个数字直接入栈）
        char sign = '+';
        for (int i = 0; i < s.length(); i++) {
            char ch = expr[i]; // 当前字符
            if (ch == ' ') continue; // 是空格，跳过
            if (Character.isDigit(ch)) { // 是数字，进行拼接
                num = num * 10 + (ch - '0');
            } else if (ch == '(') { // 是左括号，应当进入递归
                // 找到当前左括号对应的右括号
                int j = i + 1;
                int count = 1;
                while (count > 0) { // count为0时的j即是对应右括号的索引
                    if (expr[j] == ')') count--;
                    if (expr[j] == '(') count++;
                    j++;
                }
                // 使用左右括号的对应索引进行递归，计算括号内表达式
                num = solve_v1(s.substring(i + 1, j - 1));
                i = j - 1; // 计算完后更新索引（跳过计算完成的括号）
            }
            /**
             * 不能是else,否则用例不过，eg: 3+2*(1+2*(-4/(8-6)+7))
             * 遇到符号，对操作数进行相应的处理后入栈（处理上一个符号）
             */
            if (!Character.isDigit(ch) || i == s.length() - 1) {
                if (sign == '+') {
                    nums.push(num); // 上一个符号是加号，直接把操作数入栈
                } else if (sign == '-') {
                    nums.push(-1 * num); // 上一个符号是减号，操作数取反再
                } else if (sign == '*') {
                    nums.push(nums.pop() * num); // 上一个符号是乘号，把乘号前面的操作数取出来进行计算再入栈
                } else if (sign == '/') {
                    nums.push(nums.pop() / num); // 上一个符号是除号，把乘号前面的操作数取出来进行计算再入栈
                }
                sign = ch; // 把符号更新为当前符号
                num = 0; // 把操作数重置为零
            }
        }
        int res = 0;
        while (!nums.isEmpty()) {
            res += nums.pop(); // 栈内数据相加即是结果
        }
        return res;
    }
}
